# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def pathSum(self, root, sum):
        import numpy as np
        D = []
        T = [] #用来存储遍历值
        def dfs(root):
            nonlocal T
            nonlocal D
            if not root:
                return
            if (not root.right) and (not root.left):
                T.append(root.val)
                if np.sum(T) == sum:

                    D.append(T.copy())
                    T.pop()
                else:
                    T.pop()
                return
            T.append(root.val)
            dfs(root.left)
            dfs(root.right)
            T.pop()
        dfs(root)
        return D

if __name__ == '__main__':
    A1 = TreeNode(5)
    A2 = TreeNode(4)
    A3 = TreeNode(8)
    A1.right = A2
    A1.left = A3
    T = Solution()
    print(T.pathSum(A1,9))


